#include<string>
#include<vector>
#include <sstream>
#include<queue>
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Codec {
public:
std::stringstream ss;
    
    // Encodes a tree to a single string.
   std:: string serialize(TreeNode* root) {
       if (root == nullptr) return "";
        std::queue<TreeNode*> qt;
       
    qt.push(root);
       ss<<root->val<<',';
       while(!qt.empty())
       {
           TreeNode* cur = qt.front();
           if (cur->left != nullptr)
           {
               qt.push(cur->left);
               ss<<cur->left->val<<',';
           }else
           {
               ss<<"#,";
           }
           if (cur->right != nullptr)
           {
               qt.push(cur->right);
               ss<<cur->right->val<<',';
           }else
           {
               ss<<"#,";
           }
           qt.pop();
       }
       return ss.str();
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(std::string data) {
       if (data=="")return nullptr;
        TreeNode* root = new TreeNode();
       std::queue<TreeNode*> qi;
       std::vector<std::string> nodes;
       // 手动分割字符串，比使用istringstream更高效
       size_t pos = 0;
       while (pos < data.size()) {
           size_t nextPos = data.find(',', pos);
           if (nextPos == std::string::npos) nextPos = data.size();
            
           nodes.push_back(data.substr(pos, nextPos - pos));
           pos = nextPos + 1;
       }
       int n = nodes.size();
       root->val = std::stoi(nodes[0]);
       qi.push(root);
       int index = 1;
       while (!qi.empty())
       {
           TreeNode *cur = qi.front();
           if (nodes[index] == "#")
           {
               cur->left = nullptr;
           }else
           {
               cur->left = new TreeNode(std::stoi(nodes[index]));
               qi.push(cur->left);
           }
           index++;
           if (nodes[index] == "#")
           {
               cur->right = nullptr;
           }else
           {
               cur->right = new TreeNode(std::stoi(nodes[index]));
               qi.push(cur->right);
           }
           index++;
           qi.pop();
       }
       return root;
    }
    
};

